Operating SystemsApplicationHardware8GB RAMApplication 1 (4GB)Application 2 (6GB)Process ManagementMemory ManagementSecuritySchedulingCPUHard DiskRAMPrimary memoryFastslowLets only talk about single core CPU today=> At any point in time, 1 CPU can process 1 task/program Difference between Program and ProcessGeneral CPU freq: 2.5GHz => 2.5 * 10^9 operations/secIf there is an I/O operations, CPU will move on with another processThere will be an execution box, different processes will be coming and going => context switching1. process loads into RAM from HDD.2. CPU creates a PCB for each active processes.3. PCB + Processes are stored in RAM4. CPU executes process and updated PCB5. If context switching is needed => update PCB6. After execution, PCB and process in RAM are deleted.Multi-programming: (non-preemptive)CPU executing multiple programs by Context Switching.If a process is running, unless for I/o, it continues execution Multi-tasking: (preemptive)Every process in the RAM waiting for execution is given a time quotaThey take turns for executionImproves response timeBurst Time: to complete its execution on the CPUCPU Burst: spends executing on the CPU.I/O Burst: spends waiting for I/O operations to complete.Turnaround Time:from the submission of a process to the completion.Turnaround Time=Completion Time−Arrival TimeWaiting Time:spends in the ready queue waiting for CPU execution.Waiting Time = Turnaround Time − Burst TimeResponse Time:from the submission of a process until the first time the CPUis assigned to it.Response Time=First Response−Arrival TimeThroughput:#processes that are completed per unit time.CPU Utilization:% of time the CPU is busy executing processes.Scheduling TechniquesFirst-Come, First-Served (FCFS): Processed based on time of arrivalConvoy EffectShortest Job First (SJF):shortest burst time, executed first2 types: preemptive and non-preemptivestarvation of longer jobsRound Robin (RR):executed in a cyclic order, with each process getting a fixed time slice (quantum).T.Q should be chosen wisely, to avoid longer T.A.TPriority Scheduling:highest priority process executed first.2 types: preemptive and non-preemptivestarvation of lower-priority processes.Multi-processing:multi-core CPU'snot possible in single CPUMemory ManagementRAMExecutable FileProgramMultiprogrammingCPU shouldn't be idleAdd more processes to RAMHence the need to MM in RAMMemory managementContiguousNon-ContiguousContiguous:Fixed Partitioning: => Size of the partition should be decided first by the OS.=> 1 process per block.=> process size <= block sizeP1= 1MB, P2=3MB; P3=8MBP4=5MBSpace getting wasted => internal fragmentation & external fragmentationDynamic Partitioning: => no restriction from OS.=> only external fragmentation Solution to ext frag => compaction=> occurs when processes leaves RAM=> costly20MBNon-Contiguous:FULLP1= 3MB2MB4MB8MB8MB2MB1MBBreaking is process and placing it in diff places is difficult.PAGINGEach process is divided into pages.Pages are of fixed size.Page size fixed by OS => ex: 4kbDivide RAM into fixed framesFrame size == Page size Pages will be stored Non-Contiguously no fragmentationMapping of Page# and Frame# => saved in HashMap=> Page table Page# OffsetPages => process's virtual address spaceFrames => physical memory framesOffset => The location within a page.RAM: 32 KBProcess: 64 KBPage size: 4 KB#pages in virtual memory = 64 KB / 4 KB = 16 pages.#frames in physical memory = 32 KB / 4 KB = 8 frames.Virtual Address 0x1234:Page#: 0x1234 / 4 KB = 1 (Page 1)Offset: 0x1234 % 4 KB = 0x034OS checks the Page Table for mappingIf Page 1 is mapped to a frame in physical memory.=> access the frame in physical memory. If not, a page fault occurs, => OS will load Page 1 into an available frame.Consider Page1 => Frame 7Frame 7 * 4 KB (Page Size) + Offset (0x034)Physical Address: 7 * 4 KB + 0x034 = 0x7034.If page fault occurs and RAM is fullSwap an existing page from RAMRequired page will be added from HDD=> Page replacement Algo'sFirst-In-First-OutFrames: 3Page references: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3Least Recently Used7, 0, 1, 2, 0, 3, 0, 4, 2, 3Optimal Page Replacement7, 0, 1, 2, 0, 3, 0, 4, 2, 3Multi-threaded processes:Ex: Dinner at a restaurantEx: Browser: multiple tabs, download files etcProgram(HD) => Process (RAM) => Multiple threadsThread: basic unit of CPU executionThreadID: A unique ID assigned to each thread.PC (Program Counter): Address of the next instruction that the thread will executeRegister set:Values of CPU registers for the thread when it was last stopped.Stack: stored order of method execution & local variablesAll these 4 are stored in TCBTCB is linked to PCB Data is shared among different threads of same process ex: code, data etc.,Context switching is faster because of low overheadMultithreading exploits multi-processor architectureimproving concurrencyCooperating Processescan affect or be affected by other processes while executing.share data and resourcesimproved performanceInter-process Communication:Shared memory: communicate by reading and writing to a common memory space.Message passing: communicate by sending messages to each other (e.g., using pipes, message queues).But, concurrent access to shared data can create inconsistenciesProcess Synchronization:Ensures that cooperating processes share data safely & efficientlyw/o causing data inconsistency or conflicts.Example: Producer & ConsumerP1 and P2, => increment a shared counter => counter = 0Steps:Read the value of the counter from memory.Increment the value.Write the new value back to memory.Race Condition Scenario:P1 reads 0 into its local register.P2 also reads 0 into its local register.P1 increments its local copy of the counter (P1's value = 1).P2 increments its local copy of the counter (P2's value = 1).P1 writes its value (1) back to memory.P2 writes its value (1) back to memory.correct value => 2Part of the code which is accessing shared memoryis called critical section Solving critical section problem:Ask for permissionEntry section critical sectionEnd sectionRemainder sectionMutual Exclusion: Only one process can be in the critical section at a time.Progress: The processes not in their remainder sections should decide which one will enter the critical section next.No indefinite waiting for the descisionBounded Waiting: There must be a limit on how long a process waits to enter the critical section after requesting it.Solution: synchronization mechanismsPeterson's solution:works for two processes2 variables shared between processesint turnint[] flag => which processes are ready to enter C.SMutual exclusionProgress => when decision is taken, P are in entry sectionBounded waitingLocks:Hardware solutionshared lockbool TestAndSetLock(bool lock){ bool result = lock; lock=TRUE; return result;}This is an atomic operationSemaphores: uses int variablevariable access by: atomic operations wait() => P and signal() => Qs=1 wait(); // used to test P(int s){ while(s<=0); s--;}signal() // used to incQ(int s){ s++;}Mutual exclusionProgressBounded waitingProblem: Busy waitingSolution: Move the process to waiting stateThis leads to starvation and deadlockDeadLock:2 or more processes waiting for an event to occur, causedby a waiting processQ=1S=1Necessary conditions for deadlock1. Mutual Exclusion2. No preemption3. Hold & Wait4. Circular Wait Difficult to detect deadlocksDeadlock ignoranceDeadlock prevention:Negating at-least 1 of the 4 conditionsDeadlock Avoidance:Before allocating resource, check if its safe Deadlock Detection